0462. 最小操作次数使数组元素相等 II【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 中位数

1. 📝 题目描述

• leetcode

给你一个长度为 n 的整数数组 nums，返回使所有数组元素相等需要的最小操作数。

在一次操作中，你可以使数组中的一个元素加 1 或者减 1。

测试用例经过设计以使答案在 32 位 整数范围内。

---

示例 1：

输入：nums = [1,2,3]
输出：2
解释：
只需要两次操作（每次操作指南使一个元素加 1 或减 1）：
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

示例 2：

输入：nums = [1,10,2,9]
输出：16

---

提示：

• n == nums.length
• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

2. 🎯 s.1 - 中位数

c

int cmp(const void* a, const void* b) { return *(int*)a - *(int*)b; }

int minMoves2(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), cmp);
    int mid = nums[numsSize / 2];
    int res = 0;
    for (int i = 0; i < numsSize; i++) res += abs(nums[i] - mid);
    return res;
}

js

/**
 * @param {number[]} nums
 * @return {number}
 */
var minMoves2 = function (nums) {
  nums.sort((a, b) => a - b)
  const mid = nums[nums.length >> 1]
  let res = 0
  for (const num of nums) res += Math.abs(num - mid)
  return res
}

py

class Solution:
    def minMoves2(self, nums: List[int]) -> int:
        nums.sort()
        mid = nums[len(nums) // 2]
        return sum(abs(x - mid) for x in nums)

• 时间复杂度：$O(n\log n)$
• 空间复杂度：$O(\log n)$（排序开销）

算法思路：

• 将所有数移动到中位数的总操作次数最小
• 排序后取中位数，累加各元素与中位数的差的绝对值